COMMENT ⊗   VALID 00038 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00004 00002	\input macros[pap,rpg]
C00005 00003	\paper:Issues of Separation in Function Cells and Value Cells.
C00006 00004	\sect Introduction
C00009 00005	\sect Notation and Terminology 
C00018 00006	\sect Historical Perspective
C00026 00007	\sect Technical Arguments
C00031 00008	\ssect Multiple Denotations for a Single Name
C00037 00009	\ssect Referential Clarity
C00039 00010	\ssect Compiler Simplicity
C00044 00011	\ssect Higher Order Functions
C00045 00012	\ssect Abstraction Sharing
C00046 00013	\ssect Multiprocessing
C00048 00014	\ssect Number of Namespaces
C00055 00015	\ssect Macros and Name Collisions
C00064 00016	\ssect The Benefits of Macros
C00068 00017	\ssect Space Efficiency
C00085 00018	\ssect Time Efficiency
C00092 00019	\ssect Global Variables, Special Variables, and Constants
C00098 00020	\sssect An Approach to Free Functional Variables
C00103 00021	\sssect A Second Approach to Free Functional Variables
C00105 00022	\ssect Compatibility Issues
C00109 00023	\sssect Changing Existing Code
C00112 00024	\sssect Compatibility Packages
C00121 00025	\ssect Standardization
C00122 00026	\sect Non-Technical Arguments
C00123 00027	\ssect The Scheme Community
C00129 00028	\ssect The EuLisp Community
C00132 00029	\ssect The Japanese Community
C00133 00030	\ssect The Community of Small Computer Users
C00135 00031	\ssect The Common Lisp Community
C00137 00032	\ssect Can Vendors Afford the Merger?
C00140 00033	\ssect Can Users Afford the Merger?
C00143 00034	\sect Summary
C00144 00035	\sect Acknowledgments
C00145 00036	\appendix{A.}{Possible Solutions to the Macro Name Collision Problem}
C00172 00037	\appendix{B.}{High-Order Procedures for Functional Abstractions}
C00205 00038	\references
C00209 ENDMK
C⊗;
\input macros[pap,rpg]
\input verbat[pap,rpg]
\magnification\magstep1
\tolerance=2500
\def\lispone/{$\hbox{\bf Lisp}↓1$}
\def\lisptwo/{$\hbox{\bf Lisp}↓2$}
\def\lispfive/{$\hbox{\bf Lisp}↓5$}
\def\lispsix/{$\hbox{\bf Lisp}↓6$}


\paper:Issues of Separation in Function Cells and Value Cells.
\vskip .5truein
\centerline{Richard P. Gabriel}
\vskip .3truein
\centerline{Kent M. Pitman}

\sect Introduction

In 1981 the emerging Common Lisp \ref:Steele.1984. community turned to
Scheme for some of its motivation and inspiration. Adopting lexical
scoping proved one of the most important decisions the Common Lisp group
ever made.

One aspect of Scheme that was left behind, however, was a unified
namespace for functions and values, and accompanying uniform evaluation
rules for expressions in function and argument positions within the
language.  At the 1986 ACM Conference on Lisp and Functional Programming,
members of the European community involved in the design of a dialect
called EuLisp raised the issue that perhaps Common Lisp should have
adopted this paradigm and that perhaps it would still be appropriate to do
so.

Many people in the Common Lisp community were not happy about the proposed
change. Technical, philosophical, and political arguments on both sides of
the issue became quickly apparent. Since this issue has been seen to be
controversial, the Common Lisp community felt it important to clearly
document both sides in an unbiased way before attempting to make any
decision on the subject.

Scheme and EuLisp have chosen to adopt a unified namespace. Several questions
remain to be answered:

\numitem{$\bullet$} Is it technically desirable for the Common Lisp community
to change?

\numitem{$\bullet$} Is it politically desirable for the Common Lisp community
to change?

\numitem{$\bullet$} Will the Common Lisp community choose to change?

To an extent, the issue to be decided may not be simply whether the
function and value namespaces in Common Lisp will merge, but perhaps also
a larger issue of whether any of the several several Lisp
communities---Common Lisp, Scheme, and EuLisp---can or should eventually
merge.

\sect Notation and Terminology 

We will begin by establishing some standard terminology for use within
the context of this paper. The impatient reader may wish to skip this 
section and refer back to it only if he or she has a question about some term
that he or she does not understand.

A {\bf function} is anything that may correctly be given to the
\smcp{FUNCALL} or \smcp{APPLY} function and is to be executed as code when
arguments are supplied.  A {\bf non-function} is any other Lisp object.

An {\bf identifier} is the name of a symbol or a variable; this is not 
an exclusive partition.  An identifier is essentially a print name.

A {\bf symbol} is a Lisp data structure that has a value cell, a property
list, a function cell (in Common Lisp), and so on.

A {\bf variable} is an identifier that names a location.

A {\bf binding} is a pairing of an identifier with a location in which
location a Lisp object may be placed.

A {\bf lexical variable} is a binding in which the identifier is not
taken to refer to a symbol.
A symbol with a value in its value cell is taken to be a binding in that
the name of the symbol is paired with the value cell of the symbol. 
A {\bf special variable} is a binding in which the identifier {\it is} taken
to refer to a symbol. 

An {\bf environment} is the set of all bindings in existence at some given time.
We will call a subset of an environment a {\bf sub-environment}.

A {\bf namespace} is a sub-environment. Often the location parts of the
bindings in a namespace contain objects used for some purpose, and the
identifiers of the namespace are said to `name objects' used for that
purpose; if the types of objects that can be stored in the location parts
of bindings in a namespace are used for a purpose such that only objects
of a certain type can be used for that purpose, then we say that `the
objects in the namespace are restricted' to that type of object.  The
objects that are stored in the location parts of bindings in a namespace
are not necessarily restricted to first-class Lisp objects.  In this 
paper, there are two namespaces of concern, which we will term the `value
namespace' and the `function namespace.' Other namespaces include tag
names (used by \smcp{TAGBODY} and \smcp{GO}) and block names (used by
\smcp{BLOCK} and \smcp{RETURN-FROM}), but the objects in the location
parts of their bindings are not first-class Lisp objects.

The {\bf value namespace} is a sub-environment whose location parts are
not restricted to any particular kind of object.  The purpose of this
namespace is to associate values with variables when those variables occur
in certain textual contexts.  The binding of an identifier referring to a
symbol along with a value cell is in the value namespace.  Lexical
variables, such as those introduced by \smcp{LET}, \smcp{LAMBDA}, and
\smcp{MULTIPLE-VALUE-BIND}, are in the value namespace.

The {\bf function namespace} is a sub-environment whose location parts are
restricted to functions, except under error conditions.  The purpose of
this namespace is to associate functions with variables when those
variables occur in certain textual contexts.  The binding of an identifier
referring to a symbol along with a function cell is in the function
namespace. Functional lexical variables, such as those introduced by
\smcp{FLET}, \smcp{LABELS}, and \smcp{MACROLET}, are in the function
namespace.

Lisp's evaluation rules tell, given an expression and an environment, how
to produce a value or values and a new environment. In order to do this,
the meanings of identifiers in a program text need to be determined, and
this requires determining in which namespace to interpret the identifiers.
For example, a symbol can have something in its value cell and something
else in its function cell; which of these objects is referred to by the
symbol in a piece of code depends upon which namespace is defined to be
used for the context in which the symbol appears.

The Common Lisp specification defines that it is an error to place a
non-function in the function cell of a symbol. Since this is a discussion
of correct programs, it should be assumed in all objects placed in the
function cell of a symbol are valid functions unless specifically stated
otherwise.

The function and value namespaces are distinct in Common Lisp because,
given a single name, the function namespace mapping and the value
namespace mapping can yield distinct objects. The two mappings
{\it might} yield the same object, but that would be mere coincidence.

For the purposes of this document, we will refer to two abstract 
dialects of Lisp, which we shall call \lispone/ and \lisptwo/.

\lispone/ has a single namespace, which serves a dual role as the function
namespace and value namespace. That is, its function namespace and value
namespace are not distinct. In \lispone/, the functional position of a form
and an argument positions of forms are evaluated according to the same rules.
Scheme \ref:Rees.1986. and EuLisp \ref:Padget.1986. are \lispone/ dialects.

\lisptwo/ has distinct function and value namespaces. In \lisptwo/, the
rules for evaluation in the functional position of a form are distinct from
those of evaluation in the argument positions of the form.
Common Lisp is a \lisptwo/ dialect.

\sect Historical Perspective

Historically, most Lisp dialects have adopted a two-namespace approach to
the naming problem. To some extent this is because most dialects followed
Lisp 1.5 \ref:McCarthy.1965. unless there was some interesting reason not
to follow it, or else they have chosen to follow dialects derived from
Lisp 1.5.

Lisp 1.5 broke symbols into values and functions; values were stored on an
association list, and functions on the property lists of symbols.
Compiled and interpreted code worked differently from each other.  In the 
interpreter, the association list was where all bindings were kept.  When 
an identifier was encountered (an `atomic symbol' in Lisp 1.5 terminology), 
it was taken to be a variable to be evaluated for its value. First the 
\smcp{APVAL} part of the symbol was interrogated---an \smcp{APVAL} was ``{\bf A}
{\bf P}ermanent, system-defined {\bf VAL}ue'' stored in a specific place in 
the symbol. Second, the association list was searched. Finally, if neither 
of these other two possibilities found a binding, an error was signalled.

When a combination was encountered, the function position was evaluated
differently from the other positions. First, the symbol was interrogated
to see whether there was a function definition associated with the symbol,
then the association list was searched.

Here we can see two namespaces at work, though non-symbol variables (Lisp
1.5 did not have lexical variables in interpreted code) were treated
somewhat uniformly: when there were no function definitions associated with
a symbol, there was one namespace, explicitly represented by the association 
list.

Compiled code worked a little differently, and from its internals
we can see where the two namespaces came about in descendants from
Lisp 1.5, at least conceptually.

The Lisp 1.5 compiler supported `common' and `special' variables. 
A common variable enabled compiled and interpreted code to communicate
with each other. A common variable was bound on an explicit association 
list, and to evaluate such a variable a call to \smcp{EVAL} was emitted to 
determine the value.  A special variable was the compiler's modeling 
of free variables and closely matched what is called today `shallow 
binding.'  Ordinary variables were compiled into what we have termed
`lexical variables.'

Thus, we see all of the components of the two-namespace world in Lisp
1.5, along with some of the components of the one-namespace world.

The designers of Lisp 1.5 seem to have thought of function names differently
from variable names---the Lisp 1.5 interpreter looked at the property list
of the named atomic symbol first, and so it can be argued that a function
was considered a property of a function. The designers used the terminology
that a symbol `stands for' a function, while a variable `refers' to
a value.

Lisp for the PDP-6 at MIT adopted the style of the Lisp 1.5 special
variables for dynamic binding in both compiled and interpreted code,
eliminating common variables. Compilers were still written to try to
interpret special variables as lexical variables in as many places as
possible. The value of a symbol was stored in the special value cell of
the symbol and the function remained on the property list as it did in
Lisp 1.5.

MacLisp was a direct descendant of the PDP-6 Lisp, and it continued
on with the tradition of being a \lisptwo/ dialect.
MacLisp used a sophisicated form of link table, which was made possible by the
separation of namespaces. In particular, function-defining functions had
controlled access into the places where functions were stored, so that the
link tables could be correctly maintained.

Vax NIL is a descendant of MacLisp, intended to be the Lisp for the Vax in
which MacLisp-written Macsyma could be written. Macsyma code makes strong
assumptions about running in a Lisp with two namespaces, so it did not
make sense to collapse the namespaces in Vax NIL, even if the possibility
ever was raised. Moreover, the same sort of link table ideas found in
MacLisp were used here for fast function calling. The designers of MacLisp
and NIL had performance in mind when they designed the two namespace
layout.

S-1 Lisp is a dialect of NIL for the S-1 Mark IIA, and so it is a
\lisptwo/ dialect.  Spice Lisp is an intellectual descendant of MacLisp,
so it followed tradition.  ZetaLisp is an intellectual descendant of
MacLisp and, for whatever reasons, became a \lisptwo/ dialect.

Common Lisp was a compromise among a number of dialects of Lisp, most of
them descendants of MacLisp, all of them \lisptwo/s. A major aspect of the
Common Lisp movement was compromise along political lines.

\sect Technical Arguments

\ssect Notational Simplicity

Many people believe that having the function position be evaluated
differently from the argument positions in \lisptwo/ is very inelegant.
The reason that different evaluation rules are needed is because
there are different namespaces or environments for function bindings
and for value bindings. Therefore there is an evaluation rule for
each environment.  

\lisptwo/ is slightly more complicated than \lispone/ in situations where
we want to do either of the following two actions:

\numitem{$\bullet$} Fetch the value of an identifier in the value namespace
and call it as a function.

\numitem{$\bullet$} Fetch the value of an identifier in the function
namespace pass it around as a value.

To use the value of an identifier in the value namespace as a function,
\lisptwo/ provides this notation:

\begintt
(FUNCALL <identifier> . <arguments>)
\endtt

\noindent For example, in \lisptwo/ one might write

\begintt
(DEFUN MAPC-1 (F L) (DOLIST (X L) (FUNCALL F X)))
\endtt

\noindent In \lispone/, one would write

\begintt
(DEFUN MAPC-1 (F L) (DOLIST (X L) (F X)))
\endtt

To use the value of an identifier in the function namespace as a
normal value, \lisptwo/ provides this notation:

\begintt
(FUNCTION <identifier>)
\endtt

\noindent which is often abbreviated as simply 

\begintt
#'<identifier>
\endtt

\noindent For example, in \lisptwo/ one might write

\begintt
(MAPC #'PRINT '(A B C D))
\endtt

\noindent In \lispone/, one would write

\begintt
(MAPC PRINT '(A B C D))
\endtt

The differences are more striking in a larger, more complex example.
In \lisptwo/, one can write the \smcp{Y} operator as

\begintt
(DEFUN Y (F)
 ((LAMBDA (G) #'(LAMBDA (H) (FUNCALL (FUNCALL F (FUNCALL G G)) H)))
  (LAMBDA (G) #'(LAMBDA (H) (FUNCALL (FUNCALL F (FUNCALL G G)) H)))))
\endtt

\noindent while in \lispone/, one can write

\begintt
(DEFUN Y (F)
 ((LAMBDA (G) (LAMBDA (H) ((F (G G)) H)))
  (LAMBDA (G) (LAMBDA (H) ((F (G G)) H)))))
\endtt

\noindent The call to this operator in order to compute $6!$ in \lisptwo/ 
would look like

\begintt
(FUNCALL (Y #'(LAMBDA (FN)
               #'(LAMBDA (X)
                  (IF (ZEROP X) 1 (* X (FUNCALL FN (- X 1))))))) 
         6)
\endtt

\noindent In \lispone/, the same call would look like

\begintt
((Y (LAMBDA (FN)
     (LAMBDA (X)
      (IF (ZEROP X) 1 (* X (FN (- X 1)))))))
 6)
\endtt

Some argue that the \lispone/ form is easier to read because it is more concise.
Others feel that the \lisptwo/ form is easier to read because the use of functions
whose names are not constant is clearly marked.

It would not surprise us to find that the question of which is easier to
read is strongly correlated to the frequency with which a given programmer
actually passes functions as arguments or uses passed arguments functionally.
If this is an uncommon event, it is probably useful to have the incident
flagged visually. If this is a common event, the additional notation may 
quickly become cumbersome.

\ssect Multiple Denotations for a Single Name

Some people find it less confusing to have a single meaning for a name.
Fewer meanings mean less to remember.

For example, suppose a programmer has defined a function \smcp{F} as

\begintt
(DEFUN F (X) (+ X 1))
\endtt

\noindent Then suppose the programmer is writing a new function \smcp{G} and
wants it to take a functional parameter \smcp{F}, which it is to apply
to its other argument.  Suppose the programmer writes

\begintt
(DEFUN G (F) (F 3))
\endtt

Issues of defined program semantics aside, it's probably obvious that the
programmer who wrote this piece of code meant to call the function named
by the formal parameter \smcp{F} on the argument 3.  In \lisptwo/,
however, this function will ignore its argument named \smcp{F} and simply
invoke the globally defined function named \smcp{F} on 3.  Notice,
by the way, that this is precisely what Lisp 1.5 would have done.

Unfortunately, not all situations are as clear cut as this. For example, 
consider the following:

\begintt
(DEFUN PRINT-SQUARES (LIST)
  (DOLIST (ELEMENT LIST)
    (PRINT (LIST ELEMENT (EXPT ELEMENT 2)))))
\endtt

\noindent In this definition, there are three uses of the name
\smcp{LIST}. The first is in the function's formal parameter list. The
second is in initialization of the \smcp{DOLIST} variable. The third is in
the \smcp{PRINT} expression. This program, which is valid in current
Common Lisp, would not be valid in \lispone/ because the name LIST could not
simultaneously denote a list of numbers and a function. In \lispone/, a
common thing to write instead would be

\begintt
(DEFUN PRINT-SQUARES (LST)
 (DOLIST (ELEMENT LST)
   (PRINT (LIST ELEMENT (EXPT ELEMENT 2)))))
\endtt

\noindent In the function \smcp{PRINT-SQUARES}, the parameter named \smcp{LST} is
better named \smcp{LIST}.

As should be clear from these examples, the advantage of treating the
function and argument positions the same is that using parameters as
functions is made more convenient syntactically.

The disadvantage is that {\it not} using parameters as functions is made
less convenient syntactically, because parameter names must be more
carefully chosen in order to not shadow the names of globally defined
functions that will be needed in the function body.

Of course, care in naming already must be observed in \lisptwo/ in order
to assure that variable names chosen for some inner binding construct not
shadow the names of variables bound by outer binding constructs. For
example, consider:

\begintt
(DEFUN HACK-LIST (LIST)
  (LET ((LST (HACK-LIST LIST)))
    (HACK-SOME-MORE LIST LST)
    (SHUFFLE LIST LST)))
\endtt

\noindent There are two variables that could naturally be named `LIST,'
and the programmer must chose which one to so name.

Nevertheless, the degree of care required to avoid name
collisions in \lispone/ is theoretically no less than that required
in \lisptwo/, but has been statistically observed to be far more, a point to
which we will return later.

The following is a simple example of some of the important issues 
in variable naming (using mixed \lispone/ and \lisptwo/ notation):

\begintt
(DEFUN ODDITY (LIST) (LIST LIST LIST))
 
(ODDITY #'CONS)
\endtt

\noindent Depending on which way the issue is decided, the possible return
values from this function might be

\begintt
(#<SUBR CONS> . #<SUBR CONS>)
(#<SUBR CONS> #<SUBR CONS>)
\endtt

\ssect Referential Clarity

In \lisptwo/, without knowing the context, it is not possible to decide 
whether the function or the value namespace is the proper one to use.
These two forms result in different interpretations of an expression, {\it x}:

$$(x\ldots)$$

$$(\ldots x\ldots)$$

A basic `rule' of Lisp style is that code is clearest when 
the least amount of context is necessary to determine what each 
expression does. Unfortunately, that rule is violated in \lisptwo/.

In a presentation at the 1986 ACM Conference on Lisp and Functional
Programming, Steele complained that the $\alpha$ operator in 
Connection $\hbox{Machine}↑\copyright$
\ref:Steele.1986., which he wanted to implement as a simple readmacro,
was not possible to implement as he desired because of this
context problem. The problem is that the $\alpha$ operator needed to
expand differently depending on whether it was expanding in a 
functional or argument position. In \lispone/, this problem would
not have arisen. However, the problem could be solved in \lisptwo/
by introducing `lambda macros' such as those which are already
used in Zetalisp \ref:Symbolics.1986b..

\ssect Compiler Simplicity

In current Common Lisp compilers, special case code is used when
deciding which namespace mapping to use when a variable is examined
by the compiler. 

The maintainers of some Common Lisp compilers claim that a change
from \lisptwo/ to \lispone/  semantics would result in simpler, 
smaller, faster compilers. One reason for this is that knowledge 
about which namespace is in effect at any given time is often
procedurally embedded.  By merging the two namespaces, the same
pieces code can be used in more places, reducing the overall
number of places where such information is represented and ultimately
making the maintenance task simpler.

The maintainers of other Common Lisp compilers claim, however, that
a change from \lisptwo/ to \lispone/ semantics would reduce the 
complexity of their compilers little if at all---that it might
force small changes at points distributed throughout the system, 
but that overall the  compiler would not change very much.

There is some concern, however, that the overall complexity of compilers
might increase as a result of such a change. This belief is based on the
observation that the change effectively causes type information to be
lost. Specifically, for \lisptwo/ a compiler writer can assume that whatever
is in a symbol-function cell must be a function; for \lispone/ a compiler
writer cannot assume that, if a programmer has written an expression that
invokes a function associated with a symbol, that the contents of the
symbol-value cell of that symbol will be a function when the function
invocation is performed.

In \lispone/, this information sometimes may be recoverable, but the
compiler may have to perform extensive type inference to do so.  Often,
the compiler will have to take an unnecessarily conservative approach.

Consider a \lisptwo/ function such as

\begintt
(DEFUN F (X) (G X))
\endtt

\noindent Even in this simple function, we are assuming that

\begintt
(SYMBOL-FUNCTION 'G)
\endtt

\noindent is a function. When a good compiler is directed to produce safe
code, that compiler must concern itself with the question of whether this
cell will ever contain a non-function. For some computers, if the compiler
cannot show that the contents of the symbol-function cell is always a
function, then it must generate less efficient code.

Common Lisp compilers can be written assuming that symbol-function cells always
contain functions in \lisptwo/ because it is legal to forbid non-functions
from ever being placed in the symbol-function cell. For example, Vax~Lisp
\ref:Digital.1986. does this. Consequently, the Vax~Lisp compiler can safely
generate code that simply jumps to the contents of the value cell of
\smcp{G}.  In \lispone/, however, this is not possible without
introducing new declarations.

The bottom line here is not that some compilers are better than 
others, but rather that compilers may vary widely in their nature,
and, as such, the effects of the proposed change may have widely
varied effects depending upon the implementation.

\ssect Higher Order Functions

While functions, like \smcp{Y}, that directly manipulate
other functions are possible to write in either \lispone/ or \lisptwo/,
many programmers feel that \lispone/ allows one to write them more
perspicuously.  The point is that the more cumbersome notation of
\lisptwo/ does nothing to encourage and may even discourage the 
writing of such functions.

See Appendix~B for a discussion of this point.

\ssect Abstraction Sharing

In \lispone/ it is easier to define an abstract piece of code that shares
abstractions between data and functions. 
Again, all of this is possible in \lisptwo/, but it is not an
encouraged style. The problem is that it is a burden to think about which
namespace will be used for various variables.

See Appendix~B for a discussion of this point.

\ssect Multiprocessing

The functional programming style has been seen to be conducive to
multiprocessing.  That is, the functional style of programming results in
programs that are more easily rendered into a parallel style. For
evidence of this, look at typical Common Lisp programs and contrast their
style and suitability for parallelization with the same programs as they
might be written in Scheme.

By transitivity, then, since \lispone/ tends to better encourage functional 
programming style, \lispone/ is also more conducive to multiprocessing.

Of course, Common Lisp is not designed to accomodate multiprocessing and
it would take more than a unification of the function and value
namespaces to allow Common Lisp to support multiprocessing in any
serious way. At this time, integrated support of multiprocessing has not
been established as an explicit goal of Common Lisp. Nevertheless, it
seems apparent that experience with a more functional programming style
will provide a good foundation for programmers who later move to a
language that does support multiprocessing in an integrated way, so
this issue should not be overlooked.

\ssect Number of Namespaces

There are really a larger number of namespaces than just the two being
discussed here. As we noted earlier, other namespaces include at least
those of blocks and tags, and types names and declaration names are often
considered namespaces.  As such, the names \lispone/ and \lisptwo/ that we
have been using are slightly misleading.  The names \lispfive/ and
\lispsix/ might be more appropriate.

This being the case, the unification the function and value namespaces
does not accomplish as much as it might initially appear to do.  Even with
that change, the interpretation of a symbol in a Common Lisp program would
still depend on the context to disambiguate variables from symbols from
type names and so on.

On the other hand, some proponents of the change have suggested that, in
time, these other namespaces would be collapsed as well. Dialects of
Scheme have done this---some to a greater extent than others.   The hope
is that when all namespaces are reduced to a single one 
that there will be a single, simple evaluation rule for all identifiers.

In fact there are an arbitrary number of namespaces because of the
existence of functions like \smcp{GET}, \smcp{ASSOC}, and \smcp{GETHASH},
which allow users to effectively associate new kinds of information with
symbols.  Even if the underlying Lisp supports exactly one namespace,
programmers will be able to invent other namespaces for their own
use. The effect of reducing the number of namespaces in the Lisp to
one will help programmers keep track of their own namespaces, but
the ``one identifier, one meaning'' motto will not necessarily apply to user
code.

Suppose a programmer has defined a macro like this:

\begintt
(DEFMACRO ADD-AUTOMOBILE (AUTO SPECS-FN DATABASE)
 `(LET ((THE-CAR (GETHASH (QUOTE ,AUTO) *AUTO-HASH-TABLE*)))
   (ADD-AUTOMOBILE-INTERNAL THE-CAR (FUNCALL ,SPECS-FN THE-CAR) ,DATABASE)))
\endtt

\noindent Then how is interpreting the identifier \smcp{CAR-HPM}
in this form different from interpreting the other identifiers
using the built-in namespaces:

\begintt
(ADD-AUTOMOBILE CAR-HPM CURRENT-YEAR-SPECS CAR-DATABASE)
\endtt

Earlier, an argument was presented that might have left the impression
that because a \lispone/ compiler can be simpler than a \lisptwo/ compiler
there was some implied simplicity of \lispone/ over \lisptwo/.  But the
fact that compilers for a Lisp of one namespace complexity is more or less
complicated than a compiler for a Lisp of another namespace complexity is
a statement about the level of Lisp compiler technology used in the two
Lisps rather than being a statement about the abstract effect the
differing namespace complexities have.  The truth is that the additional
meanings that can be associated with symbols can and do have a very
powerful effect.

Indeed, much of the power of associative functions like \smcp{GET} derives 
from what amounts to a structured kind of pun---the fact that a single
symbol (or any object, for that matter) may have more than one kind of
information usefully associated with it. The power and importance of 
this kind of structured interplay between arbitrary namespaces is hard
to deny and probably does not warrant the level of disdain that is 
sometimes given it by Scheme enthusiasts.

\ssect Macros and Name Collisions

Macros as they exist in Common Lisp are very close to being semantically
bankrupt, and the problem would become more troublesome if
Common-Lisp-style macros were to be used in a \lispone/.  The problem is
that they expand into an expression that is composed of symbols that have
no attached semantics. When substituted back into the program, a macro
expansion could conceivably take on a quite surprising meaning depending
on the local environment.

Some symbols that ultimately appear in the expansion of a macro are
obtained, by macro definition, through its parameter list from the macro
consumer. It is therefore possible to use those symbols safely. However,
writers of macros often work on the hypothesis that additional
functional variables may be referenced in macros as if they were globally
constant. Consider the following macro definition for \lispone/ or \lisptwo/:

\begintt
(DEFMACRO MAKE-FOO (THINGS) `(LIST 'FOO ,THINGS))
\endtt

\noindent Here \smcp{FOO} is quoted, \smcp{THINGS} is taken from the
parameter list for the macro, but \smcp{LIST} is free. The writer of this
macro definition is almost certainly assuming either that \smcp{LIST} is
locally bound in the calling environment and is trying to refer to that
locally bound name, or else that \smcp{LIST} is to be treated as constant
and that the author of the code in the calling environment will know to
not locally bind \smcp{LIST}. In practice, the latter assumption is
almost always made.

If the consumer of the above macro definition writes

\begintt
(DEFUN FOO (LIST) (MAKE-FOO (CAR LIST)))
\endtt

\noindent in \lispone/, it is likely that there will be a bug in the code.

Here is another example of code that would be a problem in \lispone/:

\begintt
(DEFMACRO FIRST (LIST) `(CAR ,LIST))
(DEFMACRO REST (LIST) `(CDR ,LIST))
 
(DEFUN TEST-CAR (CAR TEST-LIST)
  "The `driver' program for Frobozz Automobile, Inc.'s
   quality assurance test."
  (DO ((TESTS TEST-LIST (REST TESTS)))
      ((NULL TESTS))
    ((FIRST TESTS) CAR)))
\endtt

It's worth emphasizing, however, that these problems come up in 
either \lispone/ or \lisptwo/. The issue is really just that they are
statistically more likely in \lispone/ since there is less contextual 
information available to help out. Here is an example of how the problem
arises in normal Common Lisp:

\begintt
(DEFMACRO FOO (X Y) `(CONS 'FOO (CONS ,X (CONS ,Y NIL))))
 
(DEFUN BAZ (X Y)
 (FLET ((CONS (X Y) (CONS Y X)))
  (FOO X Y)))
\endtt

\fix{(BAZ~1~2)} returns \fix{(((NIL~.~2)~.~1)~.~FOO)}
even though it seems that
\fix{(FOO~1~2)}
might have been intended by the programmer.

Although few implementations support its full generality in file
compilation, a strict reading of the Common Lisp specification seems to
imply that it should be acceptable to write:

\begintt
(DEFMACRO FOO (X Y) ;take a deep breath
  `(FUNCALL ',#'CONS 'FOO (FUNCALL ',#'CONS ,X (FUNCALL ',#'CONS ,Y NIL))))
 
(DEFUN BAZ (X Y)
  (FLET ((CONS (X Y) (CONS Y X)))
    (FOO X Y)))
\endtt

\noindent Here \fix{(BAZ~1~2)} should evaluate to \fix{(FOO~1~2)} just as
everyone expected. See Appendix~A for more about this style of solution
to the macro name collision problem.

Given all of this, the thoughtful reader should ask: Why do macros appear
work as often as they do?

The answer seems to be based primarily in history and statistics and not
in some theoretical foundation. In recent dialects preceding Common
Lisp, such as Maclisp \ref:Pitman.1983., it was fortunately true that there
was no \smcp{FLET}, \smcp{LABELS}, or \smcp{MACROLET}. This meant that there was
an extremely high likelihood that the function bindings of identifiers 
in the macro expander's environment would be compatible with the function 
bindings of the same identifiers in the program environment. Coupled with
the fact that the only free references that most macro expansions tend 
to make are functional, this meant that writers of macros could guess
enough information about how the expansion would be understood that fairly
reliable macro packages could be developed.

With the advent of \smcp{FLET}, \smcp{LABELS}, and \smcp{MACROLET}, the risk of
conflict is considerably higher.  The Scheme community, which has long
had constructs with power equivalent to that of forms \smcp{FLET}, has
never adopted a macro facility into the language. This is because, 
among other things, macros have generally seemed like a semantically
empty concept to many of the Scheme designers. This data is again
supportive of the argument that \lispone/ dialects are more prone to 
name collisions than \lisptwo/ dialects.

The main reason why we have not seen large numbers of problems in Common
Lisp to date may well be that most Common Lisp programmers are still
programming using a Maclisp programming style and using forms like
\smcp{FLET} and \smcp{LABELS} in only very limited ways. Those groups that
do use \smcp{FLET} and \smcp{LABELS} heavily may well be composed of
individuals who learned Lisp with Scheme and do not use macros heavily or
who understand the issues outlined here well and write macros in a
controlled manner.

It should not be surprising to find increasingly many name collision
problems reported by users of Common Lisp macros as time progresses.
A change from \lisptwo/ to \lispone/ semantics for identifiers would
very likely hasten the process.

In Appendix~A we discuss some the technical issues involved with
possible solutions to the macro name collision problem.

\ssect The Benefits of Macros

Although macros can be seen to be `semantically bankrupt,' they are at
least pragmatically useful. The concept of semantic bankruptcy is
interesting, because, for example, in a Lisp with \smcp{IF} and
\smcp{PROGN}, the additional semantic power of \smcp{COND} is null, and so
one might think that \smcp{COND} represents a bankrupt construct.  Yet
\smcp{COND} buys stylistic improvements to some Lisp code, especially code
written with \smcp{IF} and \smcp{PROGN} that would be indented too far to
the right in proper indentation style or code that would not highlight the
relationships of the conditions being tested by not placing them,
vertically, near each other as the same code written with \smcp{COND} would.

Therefore, semantically poor constructs like macros can help programmers
organize their code to be more readable, more maintainable, and to express
the abstractions in their programs in such a way that the code runs
efficiently.

Common Lisp programmers are judged on their ability to use macros
appropriately and judiciously.  Without the pervasive use of macros, a
modern Lisp programming style would not have been developed, and Lisp as a
mature programming language would have never come about.  Many people
believe that the powerful Lisp macro facility is the main reason that Lisp
has been successful over the years.

Macros have formed for basis for efficient abstraction within Lisp.
Macros can be used to optimize the code produced by examining the forms
passed to the macro definition function, and different code can be
produced depending on the shape of those forms.  Macros can be used to
define extensions to Lisp because macros enable the programmer to define
new evaluation rules.

Most programmers simply do not experience the name collision problems
mentioned in the previous section with the frequency that seems to be
appropriate to the depth of the problem, largely because of the existence
of a function namespace.  \smcp{FLET} and \smcp{LABELS} define functions,
and programmers treat function names more carefully than non-function
names.  Therefore, letting function names be freely referenced in a
macro definition is not a big problem.

There are two ways to look at the arguments regarding macros and namespaces.
The first is that a single namespace is of fundamental importance, and therefore
macros are problematic. The second is that macros are fundamental, and therefore
a single namespace is problematic.

\ssect Space Efficiency

If a symbol is used both for its value and as a function, it currently
costs no additional space. Any program that has symbols that are used to
denote distinct functions and values, however, would have to be changed.
In general, this means that some new symbols would be introduced. In most
cases, the number of new symbols introduced would not be extremely large,
but there might be pathological applications where there were exceptions.

In the Lucid Lisp system \ref:Lucid.1986., there are 14 of these symbols, and
the value cell is being used, in these cases, as a cache for an object
related to the function. In the MACSYMA system \ref:Symbolics.1986a.
there are roughly 35 out of total of 10,000 of these symbols.

Using the same name to refer to both a function and a value cell can be more
space efficient since it means adding only one additional cell to an existing
data structure that already has on the order of 5 to~10 cells anyway.

This issue can be put quantitatively.  Let $n$ be the number of symbols in
a system, let $S↓2$ be the space occupied by the average symbol in an
implementation of \lisptwo/, let $S↓1$ be the space occupied by the
average symbol in an implementation of \lispone/, and let $x$ be the
number of symbols that must be added to a system to resolve name
conflicts.  Then the space saved by having separate environments is

$$(n+x)S↓1-nS↓2$$

For example, if $n$ is 8000, $x$ is~14, $S↓1$ is~28 (bytes), and 
$S↓2$ is~32 (bytes), then the space saved by \lisptwo/ is $-31608$ (bytes).  
That is, 12\% of the symbol space used by such a \lisptwo/ implementation 
might be saved if it were made to be a \lispone/ implementation instead.
In order for there to be no net change in the amount of storage between
a two-namespace and a one-namespace Lisp, one would need over 1100 symbols
to be added to the system to resolve name conflicts.

This issue is not likely to be a major point of contention.

\ssect Time Efficiency

In \lisptwo/, a function call to a function associated with a symbol
involves indirecting through the symbol's function cell. A typical
implementation on stock hardware will look at the symbol's function cell,
which points to a piece of code, possibly with an intermediate pointer
through a procedure object, as in S-1 Lisp \ref:Brooks.1982.. 

An optimization to this is for a function call to jump directly to the
correct code object, perhaps indirecting through a link table of some
sort, but eliminating the indirection through the symbol's function cell.
In order for \smcp{DEFUN} and \smcp{SETF} of \smcp{SYMBOL-FUNCTION}  to
cause existing running code to call the redefined function, the operation
of changing a symbol's function cell must invalidate the link table or
otherwise cause the correct new link to be made.

In \lispone/, the straightforward implementation of function calling would
be to check the symbol-value cell for a valid function on each function
call.

To use the link table optimization in \lispone/, \smcp{SETQ},
rather than \smcp{SETF} of \smcp{SYMBOL-FUNCTION}, must do the invalidating
or re-linking.  Of course, only an assignment to a symbol need to be
checked.  The worst case for an implementation would be that, rather than
being open coded, \smcp{SETQ} would become a function call; in this
situation, the speed loss would be from a single instruction time to up to
about 30~instruction times.

The expected case for an implementation would be that a single \smcp{SETQ}
would become two \smcp{SETQ}s.  The implementation for this case is for
each symbol to have a hidden function cell that always contains a valid
function, perhaps a trap function.  Function calls go through the function
cell as always, but \smcp{DEFUN} and \smcp{SETQ} always manipulate both
the symbol-value cell and the function cell.  Every \smcp{SETQ} also
assigns a trap function to the function cell, so that the next function
call through that symbol runs the trap code, which would establish the
valid link to the real code or would signal an error.

On some stock hardware, tricks with the addressing hardware and word
alignment can be played to get away with having only a symbol-value cell
and not having \smcp{SETQ} take any more time than it would in
\lisptwo/.  Even with the two-\smcp{SETQ} implementation it seems unlikely
that additional overhead for \smcp{SETQ} of symbols would cause any more
than a 10\% degradation in the most pessimistic inner loop, and overall it
is unlikely to cause a very noticeable degradation in any large system.

Some people might be confused by the number and complexity of space and
time tradeoffs being discussed here. First, the reason that a
sophisticated function calling method is chosen by Lisp implementors for
stock hardware implementations is that a shorter and faster function
calling sequence can be gained using various sorts of tricks, some of them
requiring tables of information needed at the time that symbol-function
cells are updated; usually the objects used to represent compiled
functions in these implementations can be shortened as well.  The space
gained by these shortenings is balanced fairly well with the storage
needed for the tables. Second, changing from \lisptwo/ to \lispone/
results in a smaller image because of the reduction in the amount of
storage needed for symbols. Third, the additional code needed for testing
assignment of symbols decreases the speed of running code and increases
its size.  If a function cell is supported as a means of providing fast
function calling, then there is no space gained by eliminating the
function cell---each symbol still has one.

Because assignment to symbols is infrequent and because changing function
definitions associated with symbols is rare, the speed tradeoff probably
results in a negligible loss in speed, and the space tradeoff also
probably results in a small space increase.

Also, this issue is an illustration of the earlier claim that simplifying
the surface language might not always result in a simpler implementation
strategy since this is one of several ways in which the implementation might be
forced to be more complicated as a result of such a change.

\ssect Global Variables, Special Variables, and Constants

A free variable in Common Lisp is taken to be a dynamic rather than
a lexical reference. This is because there is no global lexical environment
in Common Lisp. In this code

\begintt
(DEFUN PLUS (X Y) (+ X Y))
 
(DEFUN SOMEWHAT-MORE-THAN (X) (PLUS X *SOMEWHAT*))
\endtt

\noindent the reference to \smcp{*SOMEWHAT*} is special (dynamic). On the
surface, in \lispone/, the reference to \smcp{PLUS} is free also, and so
it is special (dynamic).

When a variable is declared special, a free reference to it is to the most
recently dynamically bound value for it; and, all bindings of it become
special (dynamic) bindings.  When a variable is declared constant, free
references to it are to its permanent constant value, and compilers are
free to fold that constant into the code it emits.

We introduce the concept of global variables; when a variable is
global, free references to it are to the symbol-value cell
of the symbol named by the variable, and all bindings of it are still
lexical.

To avoid a compiler warning for the free use of variables such as
\smcp{*SOMEWHAT*}, it is common in Common Lisp to declare such variables
\smcp{SPECIAL}. In order to have compilers for \lispone/ not warn about
the free use of \smcp{PLUS}, it would be unfortunate for these to have to
be declared \smcp{SPECIAL}.  

As noted in Common Lisp the default for free variable references is
special; that is, a free variable reference is taken to be a special
variable reference. If the default in \lispone/ were made to be that free
variable references were global (lexical) then it would make sense for
a compiler to not warn about such free variable references.

\sssect An Approach to Free Functional Variables

One approach to this problem would be to introduce a new declaration that
made a variable (lexically) \smcp{GLOBAL} but not \smcp{SPECIAL}.
\smcp{DEFUN} could also be made to implicitly declare function names
\smcp{GLOBAL} implicitly.

With such a declaration, in a deep-bound \lispone/, the compiler would not
need to emit code to search the dynamic binding chain to determine what
code to invoke for \smcp{PLUS} in \smcp{SOMEWHAT-MORE-THAN}.

Given such a declaration, it would still be possible in \lispone/ to write
definitions such as:

\begintt
(DEFUN ZAP (FN X Y)
  (LET ((PLUS (LAMBDA (X Y) (MAPCAR PLUS X Y))))
    (LIST (PLUS (FN X) (FN Y)) (PLUS (FN (FN X)) (FN (FN Y))))))
\endtt

\noindent where \smcp{PLUS} is defined above,
without worrying that the \smcp{LET}-binding of \smcp{PLUS} would affect
the argument \smcp{FN}. To explain the issues a little better, we will
number the references to \smcp{PLUS} and show the definition in
a different typeface:

$$\vbox{\settabs\+\cr
\+(&DEFUN ZAP (FN X Y)\cr
\+&(&LET (($\hbox{\bf PLUS}↓1$ (LAMBDA (X Y) (MAPCAR $\hbox{\bf PLUS}↓2$ X Y))))\cr
\+&&(LIST ($\hbox{\bf PLUS}↓3$ (FN X) (FN Y)) ($\hbox{\bf PLUS}↓4$ (FN (FN X)) (FN (FN Y))))))\cr}$$

\noindent $\hbox{\bf PLUS}↓1$ is a lexical binding of the variable named
\smcp{PLUS}; $\hbox{\bf PLUS}↓2$ references the global value of
the symbol \smcp{PLUS}; $\hbox{\bf PLUS}↓3$ and $\hbox{\bf PLUS}↓4$
are lexical references to the binding of $\hbox{\bf PLUS}↓1$. If \smcp{FN}
is bound to a function that is defined like this, for instance,

$$\vbox{\settabs\+\cr
\+(DEFUN BAZ (X) ($\hbox{\bf PLUS}↓5$ X X))\cr}$$

\noindent then $\hbox{\bf PLUS}↓5$ refers to the global value of
\smcp{PLUS} rather than to the \smcp{LET}-bound value in \smcp{FOO}.
If \smcp{DEFUN} were to declare function names \smcp{SPECIAL}, then
$\hbox{\bf PLUS}↓2$ and $\hbox{\bf PLUS}↓5$ would refer to the
\smcp{SPECIAL} binding for \smcp{PLUS}, namely $\hbox{\bf PLUS}↓1$, in
this example.

\sssect A Second Approach to Free Functional Variables

A second alternative is for \smcp{DEFUN} to implicitly declare
function names constant. Redefining a function might cause some compilers
to warn that some constant function definitions had been folded into code.

A mixed approach would be for all built-in Common Lisp functions to
be declared constant, while \smcp{DEFUN} would implicitly declare function
names global.

Closely related to this issue is the fact that there is currently no
system-provided dynamic variation of \smcp{FLET} and \smcp{LABELS} in
Common Lisp, though in a non-multiprocessing environment they can be
more-or-less simulated by creative use of \smcp{UNWIND-PROTECT}. If
Common Lisp were made a \lispone/ dialect, dynamic functional variables
would be something it would get `for free.' And if their use became
popular, it might be desirable to have two kinds \smcp{DEFUN}---one that
created special definitions and another that created lexical definitions.

\ssect Compatibility Issues

A transition from \lisptwo/ semantics to \lispone/ semantics would
introduce a considerable amount of incompatibility. There is the
question of implementor problems as well as user problems.

\sssect Changing Existing Code

Large bodies of code already exist that make assumptions about the current
semantics. That code would all have to be changed. Users who did not favor
this change would likely resent the amount of work required to make the 
change, which might be non-trivial.

In some cases, mechanical techniques could diagnose which programs needed
to be changed. However, because of the pervasive use of macros and of 
automatic programming techniques, it would not be possible to do such
diagnosis with 100\% reliability in any automatic way.

Compilers could be modified to provide the user information about conflicts
as they come up as a sort of machine-gun approach to the problem. This would
address some problems in automatic programming that could not be detected by
statically examining the code that does such programming.

However, some situations are still more complicated because they do not
directly produce code. Instead, they examine and modify code. For example,
compilers, translators, macros, and code walking utilities may have
built-in assumptions about the number of namespaces; if these assumptions
are never explicitly represented, they might elude automatic techniques,
possibly leading to errors or inefficiencies later on.

\sssect Compatibility Packages

Various compatibility schemes have been proposed that claim to allow these
problems to be moderated.  For example, we might have a Common Lisp with
\lispone/ semantics with a compiler switch that allows \lisptwo/ code to
be compiled and run.  Symbols would have function cells, but possibly
represented as properties on property lists. All old Common Lisp code of
the form:

\begintt
(F ...)
\endtt

\noindent would be transformed to this:

\begintt
(FUNCALL #'F ...)
\endtt

\noindent where \smcp{FUNCTION} would look things up in the `function
cell.' \smcp{FUNCALL} would be retained in the compatibility package. A
bigger example is more convincing:

\begintt
(LET ((LIST ...))
 (LIST ...))
\endtt

\noindent would become

\begintt
(LET ((LIST ...))
 (FUNCALL #'LIST ...))
\endtt

During the transformation process, variables bound by occurrences of
\smcp{FLET} and \smcp{LABELS} in the old code would be renamed to new
names produced by \smcp{GENSYM}, and the \lispone/ versions of \smcp{FLET}
(which is \smcp{LET}) and \smcp{LABELS} would be substituted for the
function namespace versions.

Possibly some compilers already perform this transformation internally and
will be simplified after the change. And perhaps an implementor will want
to provide a real function cell for this compatibility in order to run old
code relatively fast. Lisps that normally have link tables will need to
provide separate linking code (possibly the old link code) for the
compatibility package.

This type of compatibility takes a \lisptwo/ program and produces a
\lispone/ program that uses some compatibility features for \lisptwo/
programs added to the \lispone/. In theory, the \lisptwo/ source for
the transformed program could be thrown away and then only the \lispone/
code with the compatibility features could be used in the future.

Unfortunately, there are several problems with this kind of compatibility.

First, it does not lend itself neatly to mixing compiled and interpreted
code, especially when such code is produced at runtime. It becomes
important, for example, to clearly document and control whether
functions that receive expressions to be evaluated or code-walked
are receiving expressions in \lispone/ or \lisptwo/. Since this
information is not likely to have been explicitly represented in the
data flow of the original \lisptwo/ program, and since our compatibility
scheme does not introduce new data flow to carry such information,
confusion on this point is inevitable.

Also, the compatibility package could expand expressions into code that
was opaque to certain code walkers, compilers, and macro facilities, which
might have made built in closed-world assumptions about the kinds of
expressions that were likely to come up in a particular application and
hence the kinds of properties that it would be necessary to show in order
to accomplish correct expansion. The reason that this might occur is that
the proposed translation may involve treating some forms that were
documented as special forms as if they were macros. This would mean that
code analysis routines that were expecting to see a certain class of
expressions would in fact see a different class of expressions from those
forseen by the designer of the code analysis routines.

Another problem occurs when the compatibility code uses property lists to
hold the `symbol-function' cells and the \lisptwo/ code to be translated also
uses them. In this case the running \lispone/ version of the \lisptwo/ code
might destroy part of the compatibility information.

It is clear that there is a class of \lisptwo/ programs that could be
safely run under this translation-style of compatibility. There is
also, clearly, a class of programs that require a stricter compatibility.

A second stage of compatibilty would require, essentially, a complete
implementation of the total semantics of \lisptwo/ along side, but sharing
code with, the \lispone/. For example, a `real' symbol-function cell
would need to be implemented, along with an \smcp{EVAL} and a compiler---the
compiler could be a combination of the translator mentioned above and the
\lispone/ compiler.

Finally, some programs may function correctly but suffer an efficiency
loss that is greater than the simple loss which might be assumed by just
analyzing the theoretical speed of the compatibility code. For example,
suppose a macro would be capable of performing an interesting optimization
if it could prove something about a certain side-effect within a certain
range of code.

A simple compatibility package can probably take care of a certain class of
Common Lisp programs, but for programs that would require, essentially,
an implementation of \lisptwo/ in \lispone/ for compatibility, it is probably
best to require programmers to translate those programs into \lispone/.

There is a population of Common Lisp programmers who will simply not want
to rewrite their code, and there is a body of Common Lisp code such that
the compatibility schemes require as much work to use as is required to
translate the code.

\ssect Standardization

In standardizing a language, we should take care to standardize
those things that have had proven success and acceptance by a
user community. It is often dangerous to standardize on the
most recently formulated ideas. The new macro solution by
Kohlbecker, described in Appendix~A, is of this form.

It is very tempting to the put the latest good ideas into an emerging
language design, but designing a language is a different activity from
standardizing a language: Right now we are engaged in standardization.

\vfill\eject
\sect Non-Technical Arguments

\ssect The Scheme Community

With the advent of Common Lisp, the Lisp and Scheme communities have
considerably more overlap than they have ever had in the past.

Compatibility with Scheme is not currently a goal of the Common Lisp
design committee. But, if all other things were equal, there
would be no reason for us to seek to be gratuitously incompatible with
Scheme.

If Common Lisp were to become a \lispone/ dialect, it might prove
possible to develop a layered definition in which Scheme is the base 
layer and Common Lisp is the `industrial strength' layer. Scheme
might then be a natural subset for use on smaller computers and 
embedded systems.

Of course, the Scheme community would need to be convinced that this
layering is desirable. Though the entire Scheme community has not been
involved in any discussions of the issue, some of its members have
expressed interest in the idea. Without the full support of the Scheme
community, there is no guarantee that Scheme will not later change in an
incompatible way that will coincidentally thwart such a good faith move
on the part of the Common Lisp community. Although Scheme was originally
formed to accomodate a particular set of design features that its
authors found interesting \ref:Sussman.1975., it has survived partially as a
vehicle for experimentation in more `purist' features, which might
directly conflict with the practical needs of an industrial strength
Lisp. In \ref:Rees.1986., for example, it is explicitly stated that Common
Lisp compatibility is not uppermost in the list of concerns of the
Scheme community.  A formal merger, which seems appropriate at the moment,
could later turn sour.

If we did become compatible, we would have to be careful to not constrain
the Scheme community to stick too closely to the particular definition 
of Scheme that would be this fundamental layer. 

On the other hand, the Scheme designers believe that Common Lisp has a
number of bad warts---two namespaces being foremost---and that, therefore,
compatibility is not as important as it would be if the foundations of
each dialect were more closely akin. With the willingness of the Common
Lisp community to `see the light,' perhaps the willingness to remain
compatible with the newer, merged dialects, would be greater.

If compatibility with Scheme is desired, there are other changes to Common
Lisp that are necessary or desirable. Foremost are tail recursive
semantics and \smcp{CALL-WITH-CURRENT-CONTINUATION}, in which first-class
continuations are supported. This change would be completely upwards
compatible and is not conceptually hard to implement; but, there are many
details and so it is not easy to implement.

Finally, perhaps the Scheme community would see the willingness
of the Common Lisp community to change one wart as an invitation to 
begin negotiations for eliminating the rest of the warts. In that case
we would be designing a new language rather than standardizing
an established one.

\ssect The EuLisp Community

A new community of Lisp users has emerged in Europe, rallying around a
dialect of Lisp that they call EuLisp. The EuLisp group is endeavoring 
to define a new standard for Lisp---possibly to be proposed to the ISO
community as a standard for Lisp. 

Their approach seems to be to take lessons from past and present Lisp
dialects rather than to adopt and solidify those designs:  Rather than
building on existing specifications, this group is starting anew, with all
the concomitant social pressures of developing a new Lisp dialect using a
slightly too large working group. Key member of this group are Jerome
Chailloux, Julian Padget, John Fitch, Herbert Stoyan, Giuseppe Attardi,
and Jeff Dalton.

They wish to propose a 3-level standard. At the lowest level, level~0,
is the minimal Lisp, possibly suitable for proving properties of Lisp
programs. The second level, level~1, is of the size and extent of Scheme
and is intended as the right size for small personal computers.  
The highest level, level~2, is about of the size and extent of Common Lisp.
It is intended as the industrial strength Lisp with a number of as-of-now
unspecified environmental features.

The key differences between EuLisp as it now stands and Common Lisp include
a unified variable namespace, as in \lispone/, and simplified lambda-lists
(which do not allow \smcp{\&OPTIONAL} or \smcp{\&KEY}).

At one face-to-face meeting, Chailloux and Padget stated that if Common
Lisp were to collapse the two namespaces, they might be willing to adopt
fancy lambda-lists. These two concessions are possibly enough to lay the
groundwork for a widespread set of compromises, mostly from them, on the
merger of the two communities.

Without this technical merger, a messy political battle,
unwelcome to both the Common Lisp and EuLisp communities,
might ensue.

\ssect The Japanese Community

The Japanese community seems to want to stick with Common Lisp pretty much
as it is today, according to reports from Prof. Ida. It appears that there
is a heavy commitment to the current definition in the commercial marketplace
there. The political issue seems to be that we will have a battle at the ISO
level regardless of the decision we make.

\ssect The Community of Small Computer Users

Owners of small computers who would like to run Lisp are effectively 
forced to run Scheme since implementations of Common Lisp for small 
computers are very hard to find.
This makes it appear as if Common Lisp were not designed to meet
commercial needs, because most of the commercial world uses small
computers and hardly any serious Common Lisp implementations have been
attempted even in the face of a potentially large market.

If Scheme or something like it could be incorporated as a subset or
as a fundamental lower level, it might be possible to make an 
interesting subset of Common Lisp available for users of these machines
in a useful way.

On the other hand, the average size of a `small' computer is increasing 
at a brisk pace. By the time any standard is finally approved by ANSI, 
the cost of supporting a `level 3' Common Lisp may not be prohibitive
even on `small' computers, and some argue that that day is already here.

\ssect The Common Lisp Community

The Lisp vendors have, largely, convinced the commercial world that the Lisp
community has decided to get its act together and settle on one dialect of
Lisp---Common Lisp---and that it is time to start writing commercial
products using that dialect. If the Lisp community now changes Common Lisp
in such an incompatible way, the newly-convinced commercial world
might balk.

In addition there are other parts of the Common Lisp community who
have grown to see the warts as beauty marks. For them the changes
to bring these other communities together are gratuitous. We have
to recognize that there are important segments of the Common Lisp
community who will strongly fight this change. As we should not
ignore the European and Japanese Lisp communities, so we should not
ignore the loyal Common Lisp community.

It is possible, of course, that an X3 sanction of such a change as
part of not only a US standard Lisp but an international standard 
Lisp would make it easier for vendors to accept such a change. But 
preliminary feedback from a number of large vendors and large consumers
suggests that some people consider there already to be an informal 
standard, which they would be dismayed to see changed.

\ssect Can Vendors Afford the Merger?

Most Lisp vendors have their hands full improving and honing their
products. Typically these vendors schedule tasks 6 months to a year ahead.
At the very least, if the merger takes $n$ person-months to accomplish for
some vendor, there are $n$ person-months of something else very useful that
does not get done.  If the task of the merger is on the order to of
several person-years for a vendor, that vendor might not survive the
change.  

In some cases, vendors may just decide not to support Common Lisp
and to go their own way if they feel that the changes make it no longer
an attractive or economical item to support.

Gabriel has estimated that at Lucid about 2~person-months are needed to
make the change initially followed by 4~person-months of shakedown.

Current estimates are that such change to the Symbolics Lisp environment 
would take much longer. Allowing proper time for quality assurance
and customer transition including backward compatibility, the process
could drag out for years. Symbolics does not believe that compatibility 
schemes such as those touched on in this paper are likely to offer any
significant aid in this process.

\ssect Can Users Afford the Merger?

Many users have a lot of Common Lisp code now. Symbolics users have just
undergone a major switchover from Zetalisp to Common Lisp. Even though
many of the changes are acknowledged by customers to be in their long
term best interest, they have found the transition to be painful. Part 
of the reason is that they were convinced that the change was worthwhile
by arguments that Common Lisp would remain fairly stable. If we pull the
rug out from under them with another major change, they may get pretty
nervous.

In the days of informally supported Lisps being distributed by universities,
we might have considered simply having a flag day after which things would
behave differently and have everyone simply agree to take the headache 
for the sake of some nebulous general good. Now that customers have invested
large amounts of money and perhaps entire businesses in products that depend
on the exact workings of Common Lisp, it is not likely to be so easy to
convince them to change.

Again, perhaps X3 can help by conditioning users for the switchover, and
perhaps DARPA can pay for tools to help users; for example, a codewalker
could be written that could used to parse files and to report places in
the code that require attention. However, for some customers, even this
might be too much work, too great an expense, or too impractical---too
impractical in light of existing product distribution schedules.

\sect Summary

There are compelling technical and non-technical reasons on both sides
of the issue. This paper is an attempt to outline them so that
an informed decision can be reached.

\sect Acknowledgments

The authors gratefully acknowledge useful commentary and support of Will
Clinger, Scott Fahlman, and David Moon. Appendix~A was largely written
by Will Clinger.

\vfill\eject
\noheadline
\appendix{A.}{Possible Solutions to the Macro Name Collision Problem}

With the problems with macros described earlier, one would hope that there
could be some solutions to these problems if Common Lisp were to
become a \lispone/ dialect.

There are four basic approaches to the macro name collision problem.

\numitem{1.}Do nothing.

\numitem{2.}Eliminate the Lisp features that contribute to create the
problem.

\numitem{3.}Provide linguistic support so the programmer can express
concisely what is meant.

\numitem{4.}Devise a macro definition facility and macro expansion
algorithm that enable the programmer to write macros in the current 
Common Lisp style with most of the name collision problems solved in
the `obvious' way.

In Common Lisp today, macros are implemented as if the approach to the
macro problem were approach~1.  Although all of the problems of macros
explained in this paper exist in \lisptwo/, programmers routinely and
frequently write powerful macros. In \lispone/ the potential for stumbling
into an error is greater than in a \lisptwo/, but programmers can learn to
work around the problems relatively easily.

In Common Lisp approach~2 can be implemented by removing
\smcp{FLET}, \smcp{LABELS}, and \smcp{MACROLET}. In \lispone/ approach~2
might require eliminating macros and using functions as the main
abstraction mechanism rather than macros.  The compiler can be directed to
inline code the functions that form the basis for abstraction, gaining
speed. The only aspect of macros that are not as easily modelled this way
is the optimization mentioned earlier in the section called {\it The Benefits
of Macros}.

Approach~3 requires the macro writer to write macro definitions in such
a way that they do not insert new free variables.  Instead of writing a
macro so that it inserts a free variable \fix{X}, the programmer would
write the macro so that the macro expansion time value of \fix{X} appears
as a quoted constant wherever \fix{X} would otherwise have been inserted.

For example, recall the following code for a \lispone/ dialect:

\begintt 
(DEFMACRO FIRST (LIST) `(CAR ,LIST))
(DEFMACRO REST (LIST) `(CDR ,LIST))

(DEFUN TEST-CAR (CAR TEST-LIST)
  "The `driver' program for Frobozz Automobile, Inc.'s
   quality assurance test."
  (DO ((TESTS TEST-LIST (REST TESTS)))
      ((NULL TESTS))
    ((FIRST TESTS) CAR)))
\endtt

\noindent This code suffers from the insertion of the free variable
\smcp{CAR} into a context in which \smcp{CAR} is bound.

In some Scheme implementations it is possible to write the following
to solve this problem:

\begintt 
(DEFMACRO FIRST (LIST) `(',CAR ,LIST)) 
\endtt

\noindent This is syntactically more tedious but has the obvious advantage
that there is no potential for name confusion.  In this macro, the value
of \smcp{CAR} is inserted into the resulting macro expanded form at macro
expansion time. The value is, presumably, the function that implements
\smcp{CAR}.  Nevertheless, something like this doesn't instantly answer
all technical problems.  When uses of this macro are compiled to a file,
one of two things must be output to the file and later read back in:

\numitem{a.}an object such as \smcp{\#$\langle$COMPILED-FUNCTION
CAR$\rangle$}, which is the name of a compiled code object

\numitem{b.}a representation of the compiled code object for \smcp{CAR}.

Lisp and Scheme implementations that can output only names of compiled
code objects will need to produce named functions along with references to
them in compiled code files for those functions that are incidentally
defined in macro definitions.  For example, consider the following, more
complex macro definition and use:

\begintt 
(DEFMACRO FOO (N X) `(',(LAMBDA (X) (+ X N)) ,X))

(FOO 3 Z)
\endtt

\noindent The incidental function \fix{(LAMBDA (X) (+ X N))} will need a
name.

For Lisp and Scheme implementations that output representations of code
objects into files, there is an additional problem, which is that for each
use of a macro like \smcp{FOO} there may be a separate copy of the
compiled code for the anonymous function in the macro definition.  Also,
in addition to writing the compiled code to a file, all procedures
necessary to support it must also be correctly saved and restored by the
file compiler.

One problem with outputting code objects to a file is that there is a
possibility of having multiple copies of the same code object in the Lisp
image when the file is loaded.  Some systems are able to collapse
structurally equal compiled-code objects into only one copy when the
occurrences of them are all in a single file, but this requires some work
and does not solve the problem of the same code object appearing in
multiple files.

When the speed of compiled code is important, programmers will wish their
compiler to open-code invocations of Lisp primitives like \smcp{CAR}.
Usually compilers notice such occurrences of \smcp{CAR} by recognizing
occurrences of the symbol \smcp{CAR}.  When macros indicate the invocation
of primitives like \smcp{CAR} and the approach being discussed is in
force, compilers will need to notice occurrences of \smcp{CAR} by
recognizing occurrences of the compiled code object that implements
\smcp{CAR}.  For instance, in the example above, the compiler ought to
open-code the original \smcp{CAR} operation in the \smcp{TEST-CAR} code
rather than to code a function call to \smcp{CAR}.  To do this, the
compiler must be made to understand a new set of idioms, and the size and
complexity of the compiler will possibly grow.

Even when speed of compiled code is not an issue, open coding these idioms
will help in a few cases where a code object would then not have to be
written to a file, but will not help when open coding is not desired by
the programmer either for reasons of space efficiency or modularity.

Another kind of linguistic support that would help to make approach~3 work
is a new declaration form for the purpose of declaring function definitions
to be pervasive constants.  Common Lisp implementations could then
declare all Common Lisp functions constant. The correct behavior of
\lispone/ with the built-in functions declared constant would be to signal
an error when cases like \smcp{TEST-CAR} above occur. However, functions
without this declaration would not receive the benefit of this check and
macros that need to use them would continue to be error-prone. Also, it
would be necessary for users to know which names in the language were
constant even if they did not plan to use them for their intended use.  To
such users, these names would appear to be holes in the space of available
names. For example, an automobile manufacturer would likely prefer to use
the name \smcp{FIRST} rather than \smcp{CAR} to access the first element
of a list exactly because the manufacturer would want to recycle the name
\smcp{CAR} for some other purpose.  Packages can be used to alleviate some
of these problems, but many view packages as fairly clumsy in their own
right.  If on the other hand the semantics were such that
constant declarations apply only to the scope of the constant variable,
then the constant declarations would not help the macro writer very much.

It appears that Common Lisp today offers no perfectly reliable way for
a macro to access a global variable.  In a \lispone/ dialect one could
write

\begintt 
(DEFMACRO HEAD-OF-QUEUE () `(',CAR (',SYMBOL-VALUE '*QUEUE*)))
\endtt

\noindent but the current \lisptwo/ dialect requires \smcp{FUNCALL} to be
used here, and there is no way to use the macro expansion time value of
\smcp{FUNCALL} without relying on the run time value of \smcp{FUNCALL} as
well, unless the code using this macro is compiled to a file and the
compiler writes out the code object for \smcp{FUNCALL} or unless the
compiler can open code the use of \smcp{FUNCALL}, as discussed above.  One
solution, of course, is to declare \smcp{FUNCALL} to be a constant using
the mechanism proposed above.  Another solution is to extend the \lisptwo/
dialect to use \lispone/ evaluation rules when the function position of a
function call is neither a symbol nor a lambda expression.

In general, approach~3 requires that the programmer be given a precise
way to name the environment in which to find free variable references.
One possible solution is to introduce some kind of absolute path to
variables, perhaps using first-class environments rooted in a global
lexical environment.  With such first-class environments a special form,
perhaps named \smcp{ACCESS} following MIT Scheme, would be used to access
the value of a variable in a specified environment.  This approach would
avoid most of the problems associated with quoted procedure values.

Once it is possible for the rest of the Lisp system to handle the
internal form of macros, it is time to turn our attention to
the tediousness of the syntax and ways in which it can be relieved
through automatic means.

Approach~4 can be based on a macro expansion
algorithm presented in Eugene Kohlbecker's PhD thesis
\ref:Kohlbecker.1986..  This algorithm was
designed to solve a different problem that occurs when bound variables
inserted by a macro inadvertantly capture variables of the same name
that appear in the macro call, but one of the variations
mentioned by Kohlbecker solves
the problem of free variables inserted by a macro as well.

The algorithm takes an expression as input and returns a
completely macro-expanded expression.  The algorithm operates in three
major phases.  In the first phase, it simply places a {\it time-stamp}
of $0$ on all symbols that appear in the expression; the time-stamped symbol
$V$ will be written as $V:0$ in the examples.
The time-stamping will make it possible
to distinguish between free variables that were inserted by macro
expansion and free variables that were already present in the macro
call.  All symbols must be time-stamped, whether free or bound,
whether they are variables or merely components of a data structure,
because it is impossible to tell the difference before macro expansion.
Following this time-stamping, the time-stamp counter is set to $1$.

The time-stamping is implemented by substituting a \smcp{GENSYM} for
each symbol, taking care that all occurrences of a
symbol are replaced by the same \smcp{GENSYM}.  Both the original symbol and
the time-stamp can be stored on the property list of the \smcp{GENSYM}.
What is important is that time-stamped symbols be distinguishable from
symbols that have not been time-stamped, that the time-stamp of a
time-stamped symbol can be determined, and that the original symbol
can be recovered from the time-stamped symbol.

The second phase of the algorithm
is presented in terms of a hypothetical \smcp{MACRO-EXPAND}, which roughly
corresponds to the \smcp{MACROEXPAND} function in Common Lisp.  A
companion \smcp{MACRO-EXPAND1} procedure will be assumed corresponding to
the \smcp{MACROEXPAND1}.  For simplicity, the algorithm is presented as
though all macros are global; \lispone/ is assumed also.

\smcp{MACRO-EXPAND} works by case analysis on its argument.
There are two broad cases:

Case 1.  The argument is not a macro call.  \smcp{MACRO-EXPAND}
returns the result of substituting for each subexpression the
result of calling itself recursively on the subexpression.

Case 2.  The argument is a macro call $M$.  \smcp{MACRO-EXPAND}
calls \smcp{MACRO-EXPAND1} to obtain the result $X$ of expanding the
top-level macro call and then time-stamps all unstamped symbols in
$X$ with the current value of the time-stamp counter.  It then
increments the time-stamp counter before calling itself
recursively on the time-stamped version of $X$.

The result of \smcp{MACRO-EXPAND} is a completely macro-expanded
expression in which

\numitem{a.}all symbols are time-stamped.

\numitem{b.}free variables derived from the original unexpanded
expression have a time-stamp of $0$.

\numitem{c.}free variables that have been inserted by a macro have
time-stamps greater than $0$.

\numitem{d.}bound variables that were inserted when a macro call
was expanded have time-stamps greater than the time-stamps of
all variables that appeared in the unexpanded macro call.

The third phase of the algorithm simply traverses the result of the
second phase and:

\numitem{a.}unstamps all symbols that name special forms or appear
in constant (quoted) structure.

\numitem{b.}unstamps all free variables whose time stamp is $0$.

\numitem{c.}unstamps all free variables whose time stamp is greater
than $0$.

\numitem{d.}leaves bound variables alone.

As presented above, the modified algorithm arranges for free variables
inserted by a macro to be evaluated at run time in the global environment.
However, the algorithm is fairly independent of the strategy chosen to
deal with such variables; for example, case~(c) of the third
phase could be replaced by

\numitem{c'.}unstamps all occurrences of free variables whose time
stamp is greater than $0$ and appear on the left hand side of a
\fix{SETQ}; replaces all other references to free variables whose time
stamp is greater than $0$ with \fix{(QUOTE VALUE)}, where \fix{VALUE}
is the value of the unstamped variable at macro expansion time.

Two examples show how this algorithm allows macros to be written in the
familiar style, while any necessary substitution for free variables is
performed automatically.  Suppose a macro is defined as

\begintt 
(DEFMACRO FIRST (LIST) `(CAR ,LIST))
\endtt

\noindent and the input expression is

\begintt 
(LET ((CAR '(A B C))) (FIRST CAR))
\endtt

The output of the time-stamping phase is

\begintt
(LET:0 ((CAR:0 '(A:0 B:0 C:0))) (FIRST:0 CAR:0))
\endtt

\noindent and the result of the second phase is something like

\begintt
((LAMBDA:0 (CAR:0) (CAR:1 CAR:0)) '(A:0 B:0 C:0))
\endtt

\noindent so the result of the third phase is either

\begintt
((LAMBDA (CAR:0) (CAR CAR:0)) '(A B C))
\endtt

\noindent or

\begintt
((LAMBDA (CAR:0) ('#<COMPILED-FUNCTION CAR> CAR:0)) '(A B C))
\endtt

\noindent depending on whether the third phase uses case~(c) or~(c').
\fix{CAR:0} is a \smcp{GENSYM}, so either way should work.

Kohlbecker's algorithm eliminates another common source of
bugs in macros.  Suppose that a restricted form of the OR macro were
defined via

\begintt
(DEFMACRO OR2 (X Y)
  `(LET ((V ,X))
     (IF V V ,Y)))
\endtt

\noindent Then the expression

\begintt
(OR2 NIL V)
\endtt

\noindent would actually work because it would expand into something like

\begintt
((LAMBDA (V:1) (IF V:1 V:1 V)) 	NIL)
\endtt

\noindent where V:1 is a \smcp{GENSYM}.

The following example suggests that case~(c) should be used in the
third phase rather than case~(c').  Consider the macro

\begintt 
(DEFMACRO HACK-PRINT-BASE-WRT-Q (Q)
 `(HACK-MIGHTILY *PRINT-BASE* ,Q))
\endtt

\noindent The runtime value of \smcp{*PRINT-BASE*} probably is meant here.
The algorithm cannot intuit the intention of the programmer, so linguistic
means of indicating this case---or other cases---would be needed if case
(c') were used.

There are three possible times at
which the value of a free variable inserted by a macro call could be
obtained:  macro definition time, macro expansion time, and run time.
Only one of them can be the default; macros that need to obtain the value
at another time will require the programmer to give explicit instructions.
In Common Lisp as now defined the default is run time.  The above algorithm
also defaults to run time if case (c) is used in the third phase.  If case~(c')
is used, the default is macro expansion time except on the left hand
side of an assignment where macro expansion time doesn't make sense.

One disadvantage of the
macro expansion algorithm is that it would require macros to call
an \smcp{UNSTAMP} function explicitly in some cases.  For example,
\fix{(EQ (CAR CLAUSE) 'OTHERWISE)} would need to be written as
\fix{(EQ (UNSTAMP (CAR CLAUSE)) 'OTHERWISE)}.

Finally, this macro expansion algorithm is very much
slower than the current Common Lisp macro expansion algorithm.
It is straightforward, however, to combine the second and third phases
into a single pass, and the algorithm can be modified so that the
time-stamping that occurs in phase~2 can be omitted when expanding a
standard macro that is known not to insert free identifiers.

\vfill\eject
\noheadline

\appendix{B.}{High-Order Procedures for Functional Abstractions}

This appendix was supplied by Harold Abelson, Guy Lewis Steele Jr., and
Gerald Jay Sussman. We have edited it to bring it into stylistic
compliance with the rest of this document.

Computer science is neither about computers nor is it a science.  Its
significance has little to do with computers---computers are incidental.
The real significance of computer science is that it
represents a revolution in the way we think, and in the way in which we
express what we think.  A computer language, from this perspective, is a
novel formal medium for expressing ideas about methodology, not just a way
to get a computer to perform operations.  A computer language, to be
useful, must support techniques used to control the complexity of large
systems:

\numitem{1.}We create abstractions to hide detail and to separate
specification from implementation.

\numitem{2.}We describe a design in terms of a sequence of levels of
description.  Robust design requires that, at each level, the descriptive
framework is rich enough so that small modifications of the design are
only slightly different in description.

\numitem{3.}We establish conventional interfaces that enable us to combine
standard well-understood pieces in a mix-and-match way.

These techniques are not unique to the organization of computational
systems.  They are common to all of engineering design.  Many computer
scientists regard computer science as an abstract form of engineering.  In
a computational system, the elementary pieces are idealized and completely
specified.  Thus, the complexity of a design is limited only by the mind
of the designer, not by the approximations inherent in modeling physical
reality.

Languages should describe designs in appropriate ways.  Each
language emphasizes particular aspects of designs and deemphasizes
others.

\ssect Expressing abstractions as procedures

One way to control complexity is by using abstractions to hide
details.  A design language provides a set of primitive constructs,
means by which these can be combined, and means of abstraction by
which combinations may be named and manipulated as if they were
primitive.  In programming, we often express abstractions as
procedures that capture general patterns of operations.

A framework for thinking about design must not arbitrarily limit our
ability to make abstractions.  In particular, an expressive
programming language should draw no distinction between patterns that
abstract over procedures and patterns that abstract over other kinds
of data.  Procedures must be allowed to be passed as arguments,
returned as values, and incorporated into data structures.  Procedural
data allows us to capture general methods so that we can name, analyze, and
build on them.

Mathematical constructions that involve functional
operators are naturally expressed in this way.
For example,
here is a procedure that expresses the concept of summation---summing
the values of a given function $f$ evaluated at discrete points on the interval
from $a$ to $b$:

\begintt
(define sum
  (lambda (f a next b)
    (if (> a b)
        0
        (+ (f a)
           (sum f (next a) next b)))))
\endtt

{\tt Sum} takes as its arguments the lower bound {\tt a},
the upper bound {\tt b}, the procedure {\tt f} that computes the value of
the function $f$, and the procedure {\tt next} that computes the next
point of the interval to consider.  The above definition expresses the
idea that the sum over the interval from $a$ to $b$ is 0 if $a>b$
and otherwise is equal to $f(a)$ plus the sum over the interval from
the next value after $a$ until $b$.

We can use the {\tt sum} procedure as a building block in
expressing further concepts.  For instance, the definite integral of
a function $f$ between the limits $a$ and $b$ can be approximated
numerically using the formula

$$\int↓{a}↑{b}f=\left[ f\left( a+ {dx\over 2}\right)
+f\left( a +dx+{dx\over 2}\right)+f\left( a
+2dx+{dx\over 2}\right)+\cdots \, \right] \, dx$$

\noindent and we can express this formula procedurally in terms of {\tt sum}:

\begintt
(define integral
  (lambda (f a b dx)
    (* (sum f (+ a (/ dx 2)) (lambda (x) (+ x dx)) b)
       dx)))
\endtt

Now we can use {\tt integral} as a building block in even more
general constructions.

A complex design is a sequence of levels of description.  Each level
describes how parts of the design are constructed from elements that
are regarded as primitive at that level.  The parts constructed at
each level are used as primitives at the next level.  Thus, in
designing electrical circuits, we use transistors, resistors and
capacitors to build amplifiers, filters and oscillators.  We assemble
these to make various kinds of radios and sound equipment.

If a design is to be robust, its parts must have more generality than
is needed for the particular application.  The means for combining the
parts must allow variations in the design plan, such as substituting
similar parts for one another and varying the arrangement in which
parts are combined.  This generality insures that, at any level, small
design changes can be expressed by making small changes in the
description.  A powerful design framework must therefore be more than
just a way to build hierarchies of abstractions.  It must be a
succession of languages each complete in itself.

Abstraction is therefore a facility of the greatest importance.  It is
most effective when not limited in arbitrary ways.  Just as every data
structure should ideally be ``first class,'' that is, not subject to
arbitrary limitations (such as the inability to return an array from a
procedure, an arbitrary restriction imposed by many programming
languages), we would like abstraction to be a ``first class''
facility.

Many programming languages place arbitrary restrictions on procedural
abstraction.  Some common examples of such restrictions: (1)~requiring
that a procedure be named and then referred to by name, rather than
stating its definition at the point of reference; (2)~forbidding the
defining of procedures within the text of other procedures; 
(3)~forbidding procedures as arguments or returned values of other
procedures; (4)~forbidding procedures to be components of such data
structures as records or arrays.  In some cases these prohibitions are
not absolute; it is often possible to get around a restriction through
some suitably obscure and devious programming technique, but such
tricks surely do not improve the clarity of the code.  Every such
restriction dilutes the power of abstractions by preventing them from
behaving in ways similar to the primitives of the language.

Common Lisp dilutes the power of functional abstractions
by providing a naming mechanism for functions that is distinct from
that for other values.  Communication between these
distinct namespaces requires the use of distracting special-purpose
mechanisms, namely {\tt \#'} and {\tt funcall}.
The entire point of an abstraction is that it takes a compound
notion and packages it into a single object that then behaves
as if it were a primitive object.  Functional abstractions
in Common Lisp do not behave syntactically like other primitive objects.

\ssect Abstractions facilitate implementation improvements

Abstractions are also important because they allow us to decompose a
system into pieces that can be independently constructed.  This is not
only an intellectual advantage.  It allows implementations to change
without massive analysis of monolithic code.  For example, 
the {\tt map} function is a familiar example of an abstraction of a
useful pattern of control: performing a calculation on every element
of a list and producing a list of results:

\begintt
(define map
  (lambda (f x)
    (if (null x)
        nil
        (cons (f (car x))
              (map f (cdr x))))))
\endtt

The important idea here is not that {\tt map} takes a functional
argument.  The important idea is that the pattern of control has been
separated from the details of the per-element computation; this
pattern of control can then be understood, proved correct, or modified
independently of the per-element computation.

Another common pattern of computation is the reduction of a list of
values to a single result through the application of an asssociative,
side-effect-free, binary combining operation.  (This pattern appears
in the {\tt sum} procedure shown above, which intertwines the
generation of arguments for the functon {\tt f} and the sum-reduction
of the results.)  This abstraction may also be expressed through the
use of a functional argument:

\begintt
(define reduce
  (lambda (f l)
    (if (null? (cdr l))
        (car l)
        (f (car l)
           (reduce f (cdr l))))))
\endtt

This particular implementation of the {\tt reduce} procedure happens
to impose right-associativity, and indeed forces the calls to {\tt f}
to be sequential, because every call to {\tt f} except one requires as
an argument the result of some other call to {\tt f}.  An important
advantage of abstraction is that the implementation may be modified
without changing the behavior of the overall program.  In this case we
can rely on the requirement that {\tt f} be associative and have no
side effects to produce a parallel implementation of {\tt reduce}:

\begintt
(define pairs
  (lambda (x k)
    (if (or (null? x) (null? (cdr x)))
        (k nil x)
        (pairs (cddr x)
               (lambda (p r)
                 (k (cons (list (car x) (cadr x))
                          p)
                    r))))))

(define reduce
  (lambda (f x)
    (pairs x
           (lambda (p r)
             (if (null? p)
                 (car r)
                 (reduce f
                    (append (map (lambda (z)
                                   (future (apply f z)))
                                 p)
                            r)))))))
\endtt

The {\tt pairs} procedure takes a list and returns two values (by
calling a continuation procedure {\tt k}): a list of adjacent
element-pairs, and a list of the leftover items (of which there will
be zero or one).  The idea in this implementation of {\tt reduce} is
to divide the list {\tt x} into pairs, apply {\tt f} to each pair, and
then reduce the list of results.  Note the use of the {\tt future}
construct (as defined in MultiLisp) to spawn a subtask that will
eventually produce the result of a specified computation while
allowing the main computation to proceed.

This approach organizes the calls to {\tt f} into a balanced binary tree
rather than a linear chain, allowing many calls to {\tt f} to be executed
asynchronously and in parallel.  The height of the tree of calls, and thus
the minimum time required to perform the entire reduction operation, is
logarithmic in the length of the original list.  This is potentially much
faster than the previous version, which necessarily takes time linear in
the length of the original list, though the time might be dominated by the
computation of {\tt f}.

Another parallel implementation of {\tt reduce} may be obtained by
replacing the expression {\tt (future (apply~f~z))} with simply {\tt
(apply~f~z)}, and stipulating that {\tt map} will arrange to perform
all calls to its functional argument in parallel (and similarly {\tt
pairs} must perform its work in a parallel fashion).  This version can
also operate in logarithmic time, and the parallelism will be
synchronous or asynchronous according to whether {\tt map} performs
its job synchronously or asynchronously.

If patterns of control are appropriately abstracted when a program is
first written, it is then easy to reimplement those abstractions to
take advantage of new hardware.  This will be extremely important in
the near future as parallel computers are introduced and become widely
used.  Programming languages must support such abstraction now, not
after the new hardware is introduced, if the transition is to be
smooth.

\ssect Example 1: HASHIFY

The following chunk of code takes a table abstraction and produces
another table abstraction that is more time-efficient.  It does this
by creating a hash table, each of whose entries is a table of the
given type.

\begintt
(defstruct table-abstraction maker looker-up inserter)

(define hashify
  (lambda (n table-abstraction)
    (let ((hash (hashfunction n))
          (bucket-make (maker table-abstraction))
          (bucket-lookup (looker-up table-abstraction))
          (bucket-insert! (inserter table-abstraction)))
      (define make
        (lambda ()
          (let ((hashtable (make-vector n)))
            (for-indices 0 n
                         (lambda (i)
                           (vector-set! hashtable i 
                                        (bucket-make))))
            hashtable)))
      (define lookup
        (lambda (key table)       
          (bucket-lookup key
                         (vector-ref table
                                     (hash key)))))
      (define insert!
        (lambda (key table value)
          (bucket-insert! key
                          (vector-ref table
                                      (hash key))
                          value)))
      (make-table-abstraction make lookup insert!))))
\endtt

The following chunk of code implements a table using an alist (with a
header to provide a locus for insertion).

\begintt
(define alist-table-abstraction
  (make-table-abstraction
   (lambda () (list '*alist-table*))
   (lambda (key table)
     (assq key (cdr table)))
   (lambda (key table value)
     (let ((vcell (assq key table)))
       (if vcell
           (set-value! vcell value)
           (set-cdr! table
                     (cons (make-entry key value)
                           (cdr table))))))))
\endtt

The following function, when given a hashtable size, will produce a
table abstraction implemented as a hashtable of alists.  One can then call
the maker-function of this abstraction to construct such a table.
\begintt
(define hash-table-of-alists-abstraction-generator
  (lambda (n) (hashify n alist-table-abstraction)))
\endtt

Because the result of {\tt hashify} is itself a table abstraction, it
is suitable as an argument for {\tt hashify}.
\begintt
(define two-level-hash-table-abstraction-generator
  (lambda (m n table-abstraction)
    (hashify m (hashify n table-abstraction))))
\endtt

Here is an example of its use.
\begintt
(define two-level-hash-table-of-alists-abstraction-1
  (two-level-hash-table-abstraction-generator 
    128 256 alist-table-abstraction))

(define color
  ((maker two-level-hash-table-of-alists-abstraction-1)))

((inserter two-level-hash-table-of-alists-abstraction-1)
 'sky color 'blue)

((looker-up two-level-hash-table-of-alists-abstraction-1)
 'sky color) => blue
\endtt

\ssect Example 2: MEMOIZE

We all know that the doubly recursive Fibonacci algorithm is
exponential in time and linear in space.  Although the algorithm is
really useless it illustrates the point of tree recursion quite
clearly.  It is also the algorithm that is second most likely to have
its name misspelled. 
\begintt
(define fib
  (lambda (n)
    (if (< n 2)
        n
        (+ (fib (- n 1))
           (fib (- n 2))))))
\endtt

As shown by Michie, one can often convert an exponential algorithm
into a faster one (in this case linear) by ``memoization.''  This idea
is easy to implement as an abstraction.
\begintt
(define memoize
  (lambda (f table-abstraction)
    (let ((table ((maker table-abstraction))))
      (lambda args
        (let ((entry
               ((looker-up table-abstraction) args table)))
          (if (found? entry)
              (value-in entry)
              (let ((value (apply f args)))
                ((inserter table-abstraction)
                 args table value)
                value)))))))
\endtt

\noindent This allows us to write:
\begintt
(set! fib (memoize fib alist-table-abstraction))
\endtt

Although we only need a 2~element cache as the table abstraction to
transform the algorithm into a linear one. 

\ssect Procedural abstractions are good for efficiency

It may be surprising to some that the use of higher-order
procedures can lead to several direct efficiency advantages.
Compiled code density is improved by sharing a single
copy of code rather than replicating it in many places.
For example, the use of \smcp{MAPCAR} causes the code for
controlling loops on lists to be centralized rather than replicated.
Although the savings for this small example are small
(and in some implementations even negative),
for more complex programs the payoff may be rather large.
For example, the {\tt hashify} and {\tt memoize} abstractions alow
more substantial savings.  An even more impressive example
is the transformer that converts a ring into a field by introducing
appropriate quotient objects.  Exactly the same code can serve
to transform the ring of integers into the field of rationals,
and to transform the ring of polynomials into the field of rational
functions.  Implementing this transformer as high-order procedures
allows a great deal of code to be shared.

The use of abstractions makes it easier to build compilers.  Procedural
abstraction can be used to represent a wide variety of control and data
abstractions: coroutines, continuations, actors and classes, thunks,
streams and other lazy data structures, among ohters.  Even \smcp{PROG}
and \smcp{GO} can be rendered in terms of procedures and procedure calls.
Simply by doing a good job of compiling procedural abstractions a compiler
can produce the same code for these notions as would a compiler that
treated each such construct separately as a special case.  (See
\ref:Brooks.1982.)  Even more important is the fact that new constructs
designed by the user can be compiled without having to change the guts of
the compiler.

In fact, it is often an advantage for data structures to be
represented (from the compiler's point of view) as procedural
abstractions.  For example, one can think of list pairs as follows:

\begintt
(define cons
  (lambda (x y)
    (lambda (m)
      (m x
         y
         (lambda (v) (set! x v))
         (lambda (v) (set! y v))))))
\endtt
\begintt
(define car
  (lambda (x)
    (x (lambda (a d sa sd) a))))
\endtt
\begintt
(define cdr
  (lambda (x)
    (x (lambda (a d sa sd) d))))
\endtt
\begintt
(define set-car!
  (lambda (x v)
    (x (lambda (a d sa sd) (sa v)))))
\endtt
\begintt
(define set-cdr!
  (lambda (x v)
    (x (lambda (a d sa sd) (sd v)))))
\endtt

The advantage of this formulation is that no special mechanisms need to be
invented for compiling manipulations of pairs.  The mechanisms of
manipulating procedural data can make a quick and dirty implementation
of pairs.  In fact, normal mechanisms of optimization, such as
data-flow analysis, with procedure integration, constant folding,
and dead-code elimination will yield excellent code.  For example, it
is a trivial consequence of beta-substitution in the above that
{\tt (car (cons a~b)) =~a}.

Not only compilation but also other programs that manipulate code
can be simplified when the number of primitive constructs is
minimized.  (This is the ``code-walker'' problem.)

\ssect Common Lisp discourages abstract programming

Common Lisp, despite its support of procedural objects
(solving the ``upward funarg'' problem), nevertheless
continues to discourage procedural abstraction.
There are two distinct reasons for this, one technical
and one social.

The technical difficulty is the namespace division.
This prevents names of functions from being used as
names of other kinds of data.  This is an advantage
in a style of programming (``FORTRAN'') where these types
do not interact, but is a severe handicap to programming
in a functional style.  Furthermore, having two namespaces
requires needless duplication of other mechanisms
(ordinary call and \smcp{FUNCALL}; \smcp{LET} and \smcp{FLET};
\smcp{SYMBOL-VALUE} and \smcp{SYMBOL-FUNCTION};
\smcp{DEFUN} and \smcp{DEFCONSTANT}; and so on).

The social difficulty is that because Common Lisp
discourages this important style of programming,
no one expects it to work; in particular, compilers
are expected to do a bad job on such code.
As a result, they {\it do} do a bad job, because
the compiler writers don't bother, because everyone
knows it isn't expected to work.
As a result, people think the whole \smcp{FUNCALL}/{\tt \#'}
thing doesn't matter, because ``no one really uses it anyway.''
This is a vicious cycle, and we would be much better off breaking it.

\vfill\eject
\noheadline

\references

\makeref:Abelson.1985.{H. Abelson and G.J. Sussman with J. Sussman,
\book{Structure and Interpretation of Computer Programs}, The MIT Press,
Cambridge, Massachusetts, 1985.}

\makeref:Brooks.1982.{R.A. Brooks, R.P. Gabriel, and G.L. Steele, Jr.,
\article{S-1 Common Lisp Implementation}, Proceedings of the 1982 ACM
Symposium on Lisp and Functional Programming, Pittsburgh, PA, August
1982.}

\makeref:Digital.1986.{Digital Equipment Corporation, \book{VAX LISP/VMS
User's Guide}, Maynard, MA, 1986.}

\makeref:Kohlbecker.1986.{E.E. Kohlbecker, Jr., \book{Syntactic Extensions
in the Programming Language Lisp}, PhD thesis, Indiana University, August
1986.}

\makeref:Lucid.1986.{Lucid, Inc., \book{Lucid Common Lisp Reference Manual
for the VAX}, Menlo Park, CA, 1986.}

\makeref:McCarthy.1965.{J. McCarthy, et al, \book{Lisp 1.5 Programmer's
Manual}, The MIT Press, Cambridge, Massachusetts, 1965.}

\makeref:Padget.1986.{J. Padget, et al, \article{Desiderata for the
standardisation of LISP}, Proceedings of the 1986 ACM Conference on Lisp
and Functional Programming, Cambridge, MA, August 1986.}

\makeref:Pitman.1983.{K.M. Pitman, \book{The Revised Maclisp Manual}
(Saturday Evening Edition), LCS Technical Report 295, MIT, May 1983.}

\makeref:Rees.1986.{J. Rees and W. Clinger, editors,
\book{$\hbox{Revised}↑3$ Report on the Algorithmic Language Scheme},
SIGPLAN Notices 21(12), September 1986.}

\makeref:Steele.1984.{G.L. Steele Jr., \book{Common Lisp, The Language},
Digital Press, Billerica, Massachusetts, 1984.}

\makeref:Steele.1986.{G.L. Steele Jr. and W.D. Hillis, \book{Connection
$\hbox{Machine}↑\copyright$ Lisp: Fine-Grained Parallel Symbolic
Processing}, Proceedings of the 1986 ACM Conference on Lisp and Functional
Programming, Cambridge, MA, August 1986.}

\makeref:Sussman.1975.{G.J. Sussman and G.L. Steele Jr., \book{SCHEME: An
Interpreter for Extended Lambda Calculus}, AI Memo 349, MIT, Cambridge,
MA, December 1975.}

\makeref:Symbolics.1986a.{Symbolics, Inc., \book{MACSYMA Reference
Manual}, Cambridge, MA, 1986.}

\makeref:Symbolics.1986b.{Symbolics, Inc., \book{Symbolics Common Lisp:
Language Concepts}, {\it Encyclopedia Symbolica}, Volume 2A, pp296-7,
Cambridge, MA 1986.}

\bye